package com.zwj.interview.动态规划;

/**
 * 题目：输入两个字符串，请求出它们的最长公共子序列的长度。如果从字符串s1中删除若干字符之后能得到字符串s2，
 * 那么字符串s2就是字符串s1的一个子序列。例如，从字符串"abcde"中删除两个字符之后能得到字符串"ace"，
 * 因此字符串"ace"是字符串"abcde"的一个子序列。但字符串"aec"不是字符串"abcde"的子序列。
 * 如果输入字符串"abcde"和"badfe"，那么它们的最长公共子序列是"bde"，因此输出3
 */
public class 最长公共子系列 {

    /**
     * 分析：
     * 由于输入有两个字符串，因此状态转移方程有两个参数。用函数f（i，j）表示第1个字符串中下标从0到i的子字符串（记为s1[0..i]）
     * 和第2个字符串中下标从0到j的子字符串（记为s2[0..j]）的最长公共子序列的长度。如果第1个字符串的长度是m，
     * 第2个字符串的长度是n，那么f（m-1，n-1）就是整个问题的解
     * <p>
     * 如果第1个字符串中下标为i的字符（记为s1[i]）与第2个字符串中下标为j（记为s2[j]）的字符相同，
     * 那么f（i，j）相当于在s1[0..i-1]和s2[0..j-1]的最长公共子序列的后面添加一个公共字符，也就是f（i，j）=f（i-1，j-1）+1
     * <p>
     * <p>
     * 如果字符s1[i]与字符s2[j]不相同，则这两个字符不可能同时出现在s1[0..i]和s2[0..j]的公共子序列中。
     * 此时s1[0..i]和s2[0..j]的最长公共子序列要么是s1[0..i-1]和s2[0..j]的最长公共子序列，
     * 要么是s1[0..i]和s2[0..j-1]的最长公共子序列。也就是说，此时f（i，j）是f（i-1，j）和f（i，j-1）的最大值
     * <p>
     * 可以将这个问题的状态转移方程总结为：
     * f(i-1,j-1)+1  s1[i]==s2[j]
     * f(i,j)= max(f(i-1,j),f(i,j-1)  s1[i]!=s2[j]
     * <p>
     * 当上述状态转移方程的i或j等于0时，即求f（0，j）或f（i，0）时可能需要f（-1，j）或f（i，-1）的值。
     * f（0，j）的含义是s1[0..0]和s2[0..j]这两个子字符串的最长公共子序列的长度，即第1个子字符串只包含一个下标为0的字符，
     * 那么f（-1，j）对应的第1个子字符串再减少一个字符，所以第1个子字符串是空字符串。任意空字符串和另一个字符串的公共子序列的长度都是0，
     * 所以f（-1，j）的值等于0。同理，f（i，-1）的值也等于0
     */

    //因此如果输入字符串的长度分别为m、n，那么代码中的二维数组dp的行数和列数分别是m+1和n+1。f（i，j）的值保存在“dp[i+1][j+1]”中。这种解法的空间复杂度是O（mn）

    /**
     * dp[i,j]表示s1[0..i]和s2[0..j]的最长公共子系列的长度
     */
    public int longestCommonSubSequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        /**
         * 确定遍历方向：
         *   dp[i + 1][j + 1]跟dp[i ][j]和dp[i + 1][j ] 以及  dp[i][j + 1]    有关
         *
         *                      dp[i][j + 1]      从上往下遍历
         *
         *
         *   dp[i + 1][j ]     dp[i + 1][j + 1]    从左往右遍历
         */
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                //如果text1.charAt(i) == text2.charAt(j)，说明这个字符都在公共子系列中，
                // 只要知道了dp[i,j]的公共最长子系列，那么只需要加上这个字符就行
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    //不相等的话，那么说明s1[i]和s2[j]至少有一个不在公共系列中，就需要比较一下
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[len1][len2];
    }




    /**
     * 优化：
     * 我们从上面的代码可以看到，在计算f（i，j）的值时，只依赖依赖于f（i-1，j-1）的值、f（i-1，j）的值和同一行左边f（i，j-1）的值
     * 由于计算f（i，j）的值时只需要使用上方一行的值和同一行左边的值,因此实际上只需要保存表格中的两行就可以
     */
    public int longestCommonSubSequence2(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        if (len1 < len2) {
            return longestCommonSubSequence2(text2, text1);
        }
        int[][] dp = new int[2][len2 + 1];
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                //二维数组dp只有两行，f（i，j）的值保存在“dp[（i+1）%2][j+1]”中
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[(i + 1) % 2][j + 1] = dp[i % 2][j] + 1;
                } else {
                    dp[(i + 1) % 2][j + 1] = Math.max(dp[i % 2][j + 1], dp[(i + 1) % 2][j]);
                }
            }
        }
        return dp[len1 % 2][len2];
    }

}
